#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define NTHREADS 4
#define BUFFSIZE 4*(NTHREADS)
#define DEGREE 62
#define ORDER (DEGREE)

typedef double keyType;
typedef struct BPNode{
	_Bool leaf;
	int numKeys;
	
	struct BPNode *parentNode;//for dependent root or not
	struct BPNode *prevNode;
	struct BPNode *nextNode;
	struct BPNode *childNode[2*ORDER];

	keyType keys[ORDER];
	char dataStr[ORDER][512];//这里就直接分配内存了，memcpy
}BPNode,*pBPNode;

typedef struct threadInputSet{
	pthread_mutex_t inputBufLock;
	pBPNode *root;
	keyType key;
	char string[512];
}bufInputSet;

typedef struct sbuf_t{
	pthread_mutex_t sbufLock;
	sem_t slots;
	sem_t items;
	int numItems;
	bufInputSet *pBuf[BUFFSIZE];
	int n;		//Maximum number of slots
	int head;	//
	int tail;
}sbuf_t;

sbuf_t sbuf;
//use read write lock to protect
pthread_rwlock_t fileEndFlagLock;// = PTHREAD_RWLOCK_INITIALIZER;
volatile _Bool fileEndFlag = false;


pthread_mutex_t treeLock = PTHREAD_MUTEX_INITIALIZER;
//pthread_mutex_t paraLock= PTHREAD_MUTEX_INITIALIZER;
void insert(bufInputSet *parameter);
void BPTreeInsertNotFull(BPNode *node,keyType key,char *string);
void BPTreeSplitInternal(pBPNode *tree,BPNode *parent,BPNode *node,int index);
void BPTreeSplitLeaf(pBPNode *tree,BPNode *parent,BPNode *node,int index);

void BPTreeSplitChild(BPNode *parent,BPNode *node,int index);

void printTree(BPNode *tree);

void buildTree(pBPNode *root);
void sbufInit(sbuf_t *sp,int n);
void sbufDeinit(sbuf_t *sp);
void sbufInsert(sbuf_t *sp,bufInputSet *item);
bufInputSet* sbufRemove(sbuf_t *sp);
void *thread(void *vargp);

int main(int argc,char **argv)
{
	pthread_t tid[NTHREADS];
	int error;
	BPNode *bRoot = NULL;

	pthread_rwlock_init(&fileEndFlagLock,NULL);
	sbufInit(&sbuf,BUFFSIZE);

	for(int i=0;i<NTHREADS;i++){
		error = pthread_create(&tid[i],NULL,thread,NULL);
		if(error != 0)
			perror("thread Create");
	}

	buildTree(&bRoot);

	for(int i=0;i<NTHREADS;i++){
		pthread_join(tid[i],NULL);
	}

	printTree(&bRoot);
	exit(0);
}
void sbufInit(sbuf_t *sp,int n)
{
	sp->n = n;
	sp->head = sp->tail = 0;
	sp->numItems = 0;
	//sem_init(&sp->mutex,0,1);//for locking
	pthread_mutex_init(&sp->sbufLock,NULL);
	sem_init(&sp->slots,0,n);//Initially, buf has n empty slots
	sem_init(&sp->items,0,0);//Initially, buf has zero data item;
}
void sbufDeinit(sbuf_t *sp)
{
	//free(sp->pBuf);
}
void sbufInsert(sbuf_t *sp,bufInputSet *item)
{
	sem_wait(&sp->slots);
	pthread_mutex_lock(&sp->sbufLock);
	++sp->numItems;
	//queue,enqueue,now不需要考虑queue的overflow，underflow
	sp->pBuf[sp->tail] = item;
	if(sp->tail == (sp->n-1)){
		sp->tail = 0;
	} else {
		++sp->tail;
	}
	pthread_mutex_unlock(&sp->sbufLock);
	sem_post(&sp->items);//可用的item数量加一
}
bufInputSet* sbufRemove(sbuf_t *sp)
{
	bufInputSet *item = NULL;
	int semFlag;
	//防止buffer已经空了，还有线程还在从buffer中取数据，造成死锁
	pthread_rwlock_rdlock(&fileEndFlagLock);
	_Bool endFlag =  fileEndFlag;
	pthread_rwlock_unlock(&fileEndFlagLock);
	pthread_mutex_lock(&sp->sbufLock);
	int itemsNum = sp->numItems;
	pthread_mutex_unlock(&sp->sbufLock);
	/* 可能是这边拿到endFlag还么结束，然后主线程紧接着结束了,然后这个数据就不对了 */
	if(endFlag && (itemsNum == 0)){
		return NULL;
	} else {
		do{
			semFlag = sem_trywait(&sp->items);
			
			pthread_rwlock_rdlock(&fileEndFlagLock);
			endFlag =  fileEndFlag;
			pthread_rwlock_unlock(&fileEndFlagLock);
			pthread_mutex_lock(&sp->sbufLock);
			itemsNum = sp->numItems;
			pthread_mutex_unlock(&sp->sbufLock);
		}while((semFlag==-1) && !(endFlag && (itemsNum==0)));//当满足这个条件应该跳出去
		
		if(endFlag && itemsNum == 0){
			return NULL;
		} else {
			pthread_mutex_lock(&sp->sbufLock);
			--sp->numItems;
			//queue dequeue
			item = sp->pBuf[sp->head];
			if(sp->head == (sp->n-1)){
				sp->head = 0;
			} else {
				++sp->head;
			}
			pthread_mutex_unlock(&sp->sbufLock);
			sem_post(&sp->slots);

			return item;
		}
	}
	return item;
}

void buildTree(pBPNode *root)
{
	FILE *pfile = fopen("./assgn_bplus_data.txt","r");
	if(pfile == NULL){
		perror("./assgn_bplus_data.txt");
		exit(1);
	}
	unsigned int count=0;
	keyType key;
	char keyString[128];
	char dataString[512];
	while(fscanf(pfile,"%s	%s",keyString,dataString) != EOF){
		key = atof(keyString);
		bufInputSet *pParameter = (bufInputSet *)calloc(sizeof(bufInputSet),1);
		pParameter->root = root;
		pParameter->key = key;
		strncpy(pParameter->string,dataString,512);
		//printf("%f,%s\n",pParameter->key,pParameter->string);
		sbufInsert(&sbuf,pParameter);
		if(!(++count % 5000)){
		//	printf("%d\n",count);
		}
	}
	pthread_rwlock_wrlock(&fileEndFlagLock);
	fileEndFlag = true;
	pthread_rwlock_unlock(&fileEndFlagLock);
	fclose(pfile);
}
void *thread(void *vargp)
{
	bufInputSet *tmp = NULL;
	bufInputSet parameter;
	
	while(1){
		tmp = (sbufRemove(&sbuf));
		if(tmp == NULL){
			break;
		}
		parameter = *tmp;
		free(tmp);
		//printf("thread ID%x,%f,%s\n",(int)pthread_self(),parameter.key,parameter.string);
		pthread_mutex_lock(&treeLock);
		insert(&parameter);
		pthread_mutex_unlock(&treeLock);
	}
	return NULL;
}


void printTree(BPNode *tree)
{
	BPNode *node = tree;
	while(node->childNode[0] != NULL){
		node = node->childNode[0];
	}
	while(node != NULL){
		int nums = node->numKeys;
		for(int i = 0;i < nums; i++){
			printf("%f,%s\n",node->keys[i],node->dataStr[i]);
		}
		node = node->nextNode;
	}
}
void insert(bufInputSet *parameter)
{
	pBPNode *tree = parameter->root;
	keyType key = parameter->key;
	char *string = parameter->string;

	BPNode *root = *tree;
	if(root == NULL){
		root = (pBPNode)calloc(sizeof(BPNode),1);
		if(!root){
			perror("insert--root");
			exit(1);
		}
		root->leaf = true;
		root->numKeys = 1;
		root->keys[0] = key;
		strcpy(root->dataStr[0],string);
#ifdef DEBUG_INSERT
		printf("node %f,%s\n",root->keys[0],root->dataStr[0]);
		//pause();
#endif
		*tree = root;
	}
	if(root->numKeys >= (ORDER)){
		//分配新的节点，然后分离节点
		BPNode *newParent = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newParent){
			perror("insert-newParent");
			exit(1);
		}
		newParent->leaf = false;
		newParent->numKeys = 0;
		newParent->childNode[0] = root;
		*tree = newParent;//

		BPTreeSplitChild(newParent,root,0);//newParent 是新的根节点，root是当前节点了

		BPTreeInsertNotFull(newParent,key,string);//往已经更新的根节点插入
	}
	else {
		BPTreeInsertNotFull(root,key,string);
	}
}

//把node的中间key给parent，以及分裂node
void BPTreeSplitChild(BPNode *parent,BPNode *node,int index)
{
	if(node->leaf){
		//在处理分裂出去的节点，新节点作为右节点
		BPNode *newNode = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newNode){
			perror("BPTreeSplitLeaf-newNode");
			exit(1);
		}
		newNode->leaf = true;
		//assign the parent
		newNode->parentNode = parent;
		newNode->numKeys = ORDER - ORDER/2;//lowBound
	//把node的右半部分的key转移到newNode中
		for(int i = ORDER/2; i < ORDER; i++){
			newNode->keys[i-ORDER/2] = node->keys[i];
			strcpy(newNode->dataStr[i-ORDER/2],node->dataStr[i]);
		
			node->keys[i] = 0;
			strcpy(node->dataStr[i],"#");
		}
	//resize the temporay node
		node->numKeys = (ORDER/2);
	//父节点的孩子节点
		parent->childNode[index] = node;
	//孩子的父节点assign the parent
		node->parentNode = parent;

	//处理parent,先调整父节点后半段的位置
		for(int i = parent->numKeys; i > index; --i){
			parent->childNode[i+1] = parent->childNode[i];
		}
		parent->childNode[index+1] =  newNode;
	//parent->keys[index] = node->keys[ORDER/2];
		for(int i = (parent->numKeys - 1);i >= index; --i){
			parent->keys[i+1] = parent->keys[i];
		}
		parent->keys[index] = newNode->keys[0];//alway is first key of newNode!!!!
		++parent->numKeys;
	//把leaf node连接起来!!!顺序很重要
		newNode->prevNode = node;
		if(node->nextNode != NULL){//nextNode != NULL
			node->nextNode->prevNode = newNode;
		}
		
		newNode->nextNode = node->nextNode;
		node->nextNode = newNode;
	}

	else{
		BPNode *newNode = (pBPNode)calloc(sizeof(BPNode),1);
		if(!newNode){
			perror("BPTreeSplitChild-newNode");
			exit(1);
		}
		newNode->leaf = false;
		//newNode->parentNode = parent;
		//node->parentNode = parent;
		//fix the keys of new node
		//ORDER/2-1个key
		keyType startPointValue = node->keys[ORDER/2];
		for(int i = ORDER/2; i < ORDER; i++){
			newNode->keys[i-ORDER/2] = node->keys[i+1];//需要避开中间值
		
			node->keys[i] = 0;
		}
		//resize the keys of node and new node
		node->numKeys = ORDER/2;
		newNode->numKeys = ORDER/2-1;
		//patition children for the new node
		for(int i = ORDER/2;i < ORDER; i++){
			newNode->childNode[i-ORDER/2] = node->childNode[i+1];
			newNode->childNode[i-ORDER/2]->parentNode = newNode;
			node->childNode[i+1] = NULL;
		}
		//fix children for the current node 
		//if the current node is not the root node
		if(node->parentNode != NULL){
			//assign parents
			newNode->parentNode = parent;
			//insert to parent node(root)
			//处理parent,先调整父节点后半段的位置
			for(int i = parent->numKeys; i > index; --i){
				parent->childNode[i+1] = parent->childNode[i];
			}
			parent->childNode[index+1] =  newNode;
			//parent->keys[index] = node->keys[ORDER/2];
			for(int i = (parent->numKeys - 1);i >= index; --i){
				parent->keys[i+1] = parent->keys[i];
			}
			parent->keys[index] = startPointValue;//
			++parent->numKeys;
			//new we push up the splitting one level
		}
		else {
			//create a new parent node
			parent->leaf = false;
			//assign parents,
			node->parentNode = parent;
			newNode->parentNode = parent;
			//insert child
			parent->childNode[0] = node;
			parent->childNode[1] = newNode;
			//insert the key into the keys
			parent->keys[0] = startPointValue;
			++parent->numKeys;
		}
	}
}

void BPTreeInsertNotFull(BPNode *node,keyType key,char *string)
{
	//case1 node is leaf
	if(node->leaf){
		int i = node->numKeys - 1;
		while((i >= 0) && (key < (node->keys[i]))){
			node->keys[i+1] = node->keys[i];
			strcpy(node->dataStr[i+1],node->dataStr[i]);
			--i;
		}
		node->keys[i+1] = key;
		strcpy(node->dataStr[i+1],string);
		++node->numKeys;
	}
	//case2 node is interl
	else{
		int i = node->numKeys - 1;
		while((i >= 0) && (key < node->keys[i])){
			--i;
		}
		++i;
		if(node->childNode[i]->numKeys >= ORDER){
			BPTreeSplitChild(node,node->childNode[i],i);
			if(key > node->keys[i]){
				++i;
			}
		}
		BPTreeInsertNotFull(node->childNode[i],key,string);
	}
}



